package com.leetcode.No0801;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 使序列递增的最小交换次数
 * @author: Wang Zhihua
 * @date: 2022-10-10
 */
public class Solution3 {
    public int minSwap(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int ans = 0;

        int curNum1 = nums1[0];
        int curNum2 = nums2[0];
        for (int i = 1; i < len; ++i) {
            if (curNum1 < nums1[i] && curNum2 < nums2[i]) {
                curNum1 = nums1[i];
                curNum2 = nums2[i];
            } else {
                ++ans;
                if (i == 1 || (nums2[i - 2] < curNum1 && nums1[i - 2] < curNum2)) {
                    curNum1 = nums1[i];
                    curNum2 = nums2[i];
                    swapArray(nums1, nums2, i - 1);
                    // 注意 i + 1 位置上的元素
                } else {
                    curNum2 = nums1[i];
                    curNum1 = nums2[i];
                    swapArray(nums1, nums2, i);
                }
            }
        }

        return Math.min(ans, len - ans);
    }

    public void swapArray(int[] nums1, int[] nums2, int i) {
        int x = nums1[i];
        nums1[i] = nums2[i];
        nums2[i] = x;
    }

    @Test
    public void test1() {

        int[] nums1 = new int[]{1,3,5,4};
        int[] nums2 = new int[]{1,2,3,7};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,3,5,8,9};
        nums2 = new int[]{2,1,4,6,9};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,4,4,5, 9};
        nums2 = new int[]{0,1,6,8,10};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,2,5,8,9,10,12,14,18,19,20,20,24,27,28,31,33,34,36,38};
        nums2 = new int[]{1,2,5,7,8, 9,11,17,15,16,19,21,28,29,30,31,33,34,38,39};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{3,3,8,9,10};
        nums2 = new int[]{1,7,4,6,8};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{2,3,2,5,6};
        nums2 = new int[]{0,1,4,4,5};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,3,2,4,6,11,12,15,16,17};
        nums2 = new int[]{1,1,5,7,8, 9,12,13,14,18};
        System.out.println(minSwap(nums1, nums2));
    }
}
